#include "BTreeNode.h"
#include <iostream>
#include <cstdlib>

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	char buffer[PageFile::PAGE_SIZE];
	pf.read(pid, buffer);
	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	char buffer[PageFile::PAGE_SIZE];
	pf.write(pid, buffer);
	return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the nod
 */
int BTLeafNode::getKeyCount()
{ 
	int count = -1;
    int p = 1;
    while (p!= '\0')
    {
		count++;
		p = *keys[count];
    }       

	return count; 
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	int keyPos = getKeyCount();
	if (getKeyCount() == 0) //if node is empty
	{
		*keys[0] = key;
		*rids[0] = rid;
	}
		else
		{
			for(int i = 0; i < getKeyCount(); i++) //for nodes with key count > 0
			{
				if(*keys[i] > key) //find position where the key should be inserted
				{
					keyPos = i;
					break;
				}
			}

			int newLength = getKeyCount();
			for(int j = newLength; j > keyPos; j--) //shift every element after the insertion position to the right
			{
				*keys[j] = *keys[j-1];
				*rids[j] = *rids[j-1];
			}

			*keys[keyPos] = key;
			*rids[keyPos] = rid;
		}
	return 0; 
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	insert(key, rid);

	int middleKey = getKeyCount()/2;

	siblingKey = *keys[middleKey];

	int oldLength = getKeyCount();

	for(int i = middleKey; i < oldLength; i++) //insert keys and rids after the middle key of first sibling node into second sibling node
	{
		*sibling.keys[i-middleKey] = *keys[i];
		*sibling.rids[i-middleKey] = *rids[i];
	}
	for(int i = middleKey; i < oldLength; i++) //make key values after the middle key in first sibling node null
	{
		*keys[i] = '\0';
	}

	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int largerKey = getKeyCount();
	for(int i = 0; i < getKeyCount(); i++) 
	{
		if(*(keys[i]) >= searchKey)
		{
			largerKey = i;
			break;
		}
	}
	eid = largerKey;

	if(largerKey == getKeyCount())
	{
		cout << "Error: cannot find larger or equal key" << endl;
	}
	return 0; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	key = *(keys[eid]);
	rid = *(rids[eid]);
	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	return lastPid; 
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	lastPid = pid;
	return 0; 
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	char buffer[PageFile::PAGE_SIZE];
	pf.read(pid, buffer);
	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	char buffer[PageFile::PAGE_SIZE];
	pf.write(pid, buffer);
	return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	int count = -1;
    int p = 1;
    while (p!= '\0')
    {
		count++;
		p = *(keys[count]);
    }       

	return count;  
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	int keyPos = getKeyCount();
	for(int i = 0; i < getKeyCount(); i++) //for nodes with key count > 0
	{
		if(*keys[i] > key) //find position where the key should be inserted
		{
			keyPos = i;
			break;
		}
	}

	int newLength = getKeyCount();
	for(int j = newLength; j > keyPos; j--) //shift every element after the insertion position to the right
	{
		*keys[j] = *keys[j-1];
		*pids[j+1] = *pids[j];
	}
	
	*pids[keyPos+1] = *pids[keyPos];

	*keys[keyPos] = key;
	*pids[keyPos] = pid;

	return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	insert(key, pid);

	int middleKey = getKeyCount()/2;

	midKey = *keys[middleKey];

	for(int i = middleKey+1; i < getKeyCount(); i++) //insert keys and rids after the middle key of first sibling node into second sibling node
	{
		*sibling.keys[i-middleKey-1] = *keys[i];
		*sibling.pids[i-middleKey-1] = *pids[i];
	}
	*sibling.pids[getKeyCount()-middleKey-1] = *pids[getKeyCount()];

	int oldLength = getKeyCount();
	for(int i = middleKey; i < oldLength; i++) //make key values after the middle key in first sibling node null
	{
		*keys[i] = '\0';
	}

	//insert midkey into parent node
	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	int keyPos = getKeyCount();
	for(int i = 0; i < getKeyCount(); i++)
	{
		if(*keys[i] >= searchKey) //find position where the search key should be
		{
			keyPos = i;
			break;
		}
	}
	pid = *pids[keyPos];
	return 0; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	*keys[0] = key;
	*pids[0] = pid1;
	*pids[1] = pid2;
	return 0; 
}
